      1  import java.util.Scanner;

      2  import java.util.Stack;

      3

      4  /**

      5     This program evaluates arithmetic expressions, using two stacks.

      6  */

      7  public class ExpressionCalculator

      8  {

      9     public static void main(String[] args)

     10     {

     11        Scanner in = new Scanner(System.in);

     12        System.out.print("Enter an expression: ");

     13        String expression = in.nextLine().replace(" ", "");

     14

     15        Stack<Integer> numstack = new Stack<Integer>();

     16        Stack<Character> opstack = new Stack<Character>();

     17

     18        int pos = 0;

     19        while (pos < expression.length())

     20        {

     21           char ch = expression.charAt(pos);

     22           pos++;

     23           if (isOperator(ch))

     24           {

     25              if (opstack.size() == 0) { opstack.push(ch); }

     26              else

     27              {

     28                 char oldOp = opstack.pop();

     29                 if (precedence(ch) > precedence(oldOp)) { opstack.push(oldOp); }

     30                 else { evaluateTop(numstack, oldOp); }

     31                 opstack.push(ch);

     32              }

     33           }

     34           else if (ch == '(') { opstack.push(ch); }

     35           else if (ch == ')')

     36           {

     37              boolean done = false;

     38              while (!done)

     39              {

     40                 if (opstack.size() == 0) { error("No matching ("); }

     41                 char oldOp = opstack.pop();

     42                 if (oldOp == '(') { done = true; }

     43                 else { evaluateTop(numstack, oldOp); }

     44              }

     45           }

     46           else if (Character.isDigit(ch))

     47           {

     48              int start = pos - 1;

     49              while (pos < expression.length()

     50                 && Character.isDigit(expression.charAt(pos))) { pos++; }

     51              String num = expression.substring(start, pos);

     52              numstack.push(Integer.parseInt(num));

     53           }

     54           else { error ("Number, operator, or parenthesis expected."); }

     55        }

     56        while (opstack.size() > 0)

     57        {

     58           char oldOp = opstack.pop();

     59           if (oldOp == '(') { error("No matching )"); }

     60           else { evaluateTop(numstack, oldOp); }

     61        }

     62        if (numstack.size() == 0) { error("Syntax error"); }

     63        System.out.println(numstack.pop());

     64        if (numstack.size() > 0) { error("Syntax error"); }

     65     }

     66

     67     /**

     68        Tests if a token is an operator.

     69        @param s the token

     70        @return true if s is one of: + - * / ^

     71     */

     72     public static boolean isOperator(char ch)

     73     {

     74        return ch == '+' || ch == '-' || ch == '*' || ch == '/';

     75     }

     76

     77     /**

     78        Prints an error message and exits.

     79        @param message information about the error

     80     */

     81     public static void error(String message)

     82     {

     83        System.out.println("ERROR: " + message + ".");

     84        System.exit(1);

     85     }

     86

     87     /**

     88        Computes the precedence level of an operator.

     89        @param s the operator

     90        @return the precedence level (1 = lowest, 3 = highest)

     91     */

     92     public static int precedence(char ch)

     93     {

     94        if (ch == '+' || ch == '-') { return 1; }

     95        else if (ch == '*' || ch == '/') { return 2; }

     96        else { return 0; }

     97     }

     98

     99     /**

    100        Computes a new value and pushes it on the stack.

    101        @param num the stack for the operands and result

    102        @param op the operation to use

    103     */

    104     public static void evaluateTop(Stack<Integer> num, char op)

    105     {

    106        if (num.size() == 0) { error("Syntax error"); }

    107        int y = num.pop();

    108        if (num.size() == 0) { error("Syntax error"); }

    109        int x = num.pop();

    110        int z = 0;

    111        if (op == '*') { z = x * y; }

    112        else if (op == '/')

    113        {

    114           if (y == 0) { error("Divide by 0"); }

    115           else { z = x / y; }

    116        }

    117        else if (op == '+') { z = x + y; }

    118        else if (op == '-') { z = x - y; }

    119        else { error("Syntax error"); }

    120        num.push(z);

    121     }

    122  }